#include <matrix_fill_lacunae.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include "matrix.h"
using std::vector;
using std::cerr;
using std::max;
using std::min;
using namespace bcpp_matrix;

// for each non a-c node
// e.g. b
// find max(a-b b-c)
// min of all is missing value
bool get_non_ultrametric_lacunae (t_sparse_matrix_f& matrix, unsigned i, unsigned j, float& value)
{
	value = std::numeric_limits<float>::max();
	bool filled_hole = false;
	
	// get all possible k and l
	vector<unsigned> non_nulls;
	for (unsigned k = 0; k < matrix.size() ; ++k)
	{
		if (k == i || k == j)
			continue;
		if (matrix.is_missing(i, k) ||
			matrix.is_missing(j, k))
			continue;
		non_nulls.push_back(k);
	}
	
	for (unsigned kk = 0; kk + 1 < non_nulls.size(); ++kk)
		for (unsigned ll = kk + 1; ll < non_nulls.size(); ++ll)
	{
		unsigned k = non_nulls[kk];
		unsigned l = non_nulls[ll];
		if (matrix.is_missing(k, l))
			continue;
		float len = max(matrix.matrix(i,k) + matrix.matrix(j,l), 
						matrix.matrix(k,j) + matrix.matrix(i,l)) - matrix.matrix(k,l);
		if (len > 0)
		{
			value = std::min(len, value);
			filled_hole = true;
		}
	}
	return filled_hole;
}


// for each 2 non a-c node
// e.g. b d
// take max(a-b + c-d, b-c + a-d) - b-d
bool get_ultrametric_lacunae (t_sparse_matrix_f& matrix, unsigned i, unsigned j, float& value)
{
	value = std::numeric_limits<float>::max();
	bool filled_hole = false;
	for (unsigned k = 0; k < matrix.size() ; ++k)
	{
		if (k == i || k == j)
			continue;
		if (matrix.is_missing(i, k) ||
			matrix.is_missing(j, k))
			continue;
		//float max_v = ;
		value = std::min(value, static_cast<float>(std::max(matrix.matrix(i,k), matrix.matrix(j,k))));
		filled_hole = true;
	}
	return filled_hole;
}

// fill lacunae using
// Landry P.-A., Lapointe F.-J. & Kirsch J.A.W. 1996.
// Estimating phylogenies from lacunose distance matrices:
// additive is superior to ultrametric estimation. Molecular Biology and Evolution 13: 818-823.
//Lapointe F.-J. & Kirsch J.A.W. 1995. Estimating phylogenies from lacunose distance matrices, with special reference to DNA hybridization data. Molecular Biology and Evolution 12: 266-284.
void fill_lacunae(t_sparse_matrix_f& matrix)
{
	for (unsigned i = 0; i < matrix.size() - 1 ; ++i)
		for (unsigned j = i + 1; j < matrix.size(); ++j)
	{
		if (!matrix.is_missing(i, j))
			continue;
		// try and fill lacunae using non-ultrametric first
		float f;
		if (get_non_ultrametric_lacunae(matrix, i, j, f))
		{
			matrix.matrix(i,j) =
			matrix.matrix(j,i) = f;
			continue;
		}
		// try and fill lacunae using ultrametric
		if (get_ultrametric_lacunae(matrix, i, j, f))
		{
			matrix.matrix(i,j) =
			matrix.matrix(j,i) = f;
		}
	}
}

